<!doctype html><html lang=en-us><head><meta charset=utf-8><meta name=viewport content="width=device-width,initial-scale=1"><meta name=description content="问题引入 给定 $64$ 位有符号整数 $a,b,m$ （类型为 int64_t），希望求出 $a\times b \bmod m$ 的数值。
int64_t multimod(int64_t a, int64_t b, int64_t m); 给出一个尽可能高效的正确 multimod 实现。使得它对于任意在 $[0,2^{63}-1]$ 范围内的 $a,b,m$ 均能正确求出 $a\times b \bmod m$ 的数值，且在任何时候不触发有符号整数溢出。
解决方法 运行环境 Windows 10 （64 位） 上 Hyper-V 平台，Debian 9 虚拟机 （64 位）
 CPU 型号：Intel(R) Core(TM) i7-7700HQ CPU 主频：2.80 GHz  基础设施 为使实验顺利，实验前先准备了测试程序和时间测量程序。
测试程序 使用 Python 自动生成测试用例，运行程序，检查输出。
import os import random import sys def getNum(): return random.randint(0,2**63-1) if __name__==&amp;#34;__main__&amp;#34;: cnt = 10**4; passed = 0 failed = 0 if len(sys."><title>64位有符号数乘法取模问题</title><link rel=canonical href=https://stardustdl.gitee.io/posts/learning/multimod-64bit-method/><link rel=stylesheet href=/scss/style.min.css><meta property="og:title" content="64位有符号数乘法取模问题"><meta property="og:description" content="问题引入 给定 $64$ 位有符号整数 $a,b,m$ （类型为 int64_t），希望求出 $a\times b \bmod m$ 的数值。
int64_t multimod(int64_t a, int64_t b, int64_t m); 给出一个尽可能高效的正确 multimod 实现。使得它对于任意在 $[0,2^{63}-1]$ 范围内的 $a,b,m$ 均能正确求出 $a\times b \bmod m$ 的数值，且在任何时候不触发有符号整数溢出。
解决方法 运行环境 Windows 10 （64 位） 上 Hyper-V 平台，Debian 9 虚拟机 （64 位）
 CPU 型号：Intel(R) Core(TM) i7-7700HQ CPU 主频：2.80 GHz  基础设施 为使实验顺利，实验前先准备了测试程序和时间测量程序。
测试程序 使用 Python 自动生成测试用例，运行程序，检查输出。
import os import random import sys def getNum(): return random.randint(0,2**63-1) if __name__==&amp;#34;__main__&amp;#34;: cnt = 10**4; passed = 0 failed = 0 if len(sys."><meta property="og:url" content="https://stardustdl.gitee.io/posts/learning/multimod-64bit-method/"><meta property="og:site_name" content="StardustDL's Blog"><meta property="og:type" content="article"><meta property="article:section" content="Posts"><meta property="article:published_time" content="2018-10-25T17:30:22+08:00"><meta property="article:modified_time" content="2018-10-25T17:30:22+08:00"><meta name=twitter:title content="64位有符号数乘法取模问题"><meta name=twitter:description content="问题引入 给定 $64$ 位有符号整数 $a,b,m$ （类型为 int64_t），希望求出 $a\times b \bmod m$ 的数值。
int64_t multimod(int64_t a, int64_t b, int64_t m); 给出一个尽可能高效的正确 multimod 实现。使得它对于任意在 $[0,2^{63}-1]$ 范围内的 $a,b,m$ 均能正确求出 $a\times b \bmod m$ 的数值，且在任何时候不触发有符号整数溢出。
解决方法 运行环境 Windows 10 （64 位） 上 Hyper-V 平台，Debian 9 虚拟机 （64 位）
 CPU 型号：Intel(R) Core(TM) i7-7700HQ CPU 主频：2.80 GHz  基础设施 为使实验顺利，实验前先准备了测试程序和时间测量程序。
测试程序 使用 Python 自动生成测试用例，运行程序，检查输出。
import os import random import sys def getNum(): return random.randint(0,2**63-1) if __name__==&amp;#34;__main__&amp;#34;: cnt = 10**4; passed = 0 failed = 0 if len(sys."><link rel="shortcut icon" href=/favicon.png><script type=application/javascript>var doNotTrack=!1;doNotTrack||(function(a,e,f,g,b,c,d){a.GoogleAnalyticsObject=b,a[b]=a[b]||function(){(a[b].q=a[b].q||[]).push(arguments)},a[b].l=1*new Date,c=e.createElement(f),d=e.getElementsByTagName(f)[0],c.async=1,c.src=g,d.parentNode.insertBefore(c,d)}(window,document,'script','https://www.google-analytics.com/analytics.js','ga'),ga('create','UA-111573521-1','auto'),ga('send','pageview'))</script></head><body class="article-page has-toc"><script>(function(){const a='StackColorScheme';localStorage.getItem(a)||localStorage.setItem(a,"auto")})()</script><script>(function(){const b='StackColorScheme',a=localStorage.getItem(b),c=window.matchMedia('(prefers-color-scheme: dark)').matches===!0;a=='dark'||a==='auto'&&c?document.documentElement.dataset.scheme='dark':document.documentElement.dataset.scheme='light'})()</script><div class="container main-container flex
extended"><div id=article-toolbar><a href=/ class=back-home><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-chevron-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><polyline points="15 6 9 12 15 18"/></svg><span>Back</span></a></div><main class="main full-width"><article class=main-article><header class=article-header><div class=article-details><header class=article-category><a href=/categories/learning/>Learning</a></header><h2 class=article-title><a href=/posts/learning/multimod-64bit-method/>64位有符号数乘法取模问题</a></h2><footer class=article-time><div><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><path d="M11.795 21H5a2 2 0 01-2-2V7a2 2 0 012-2h12a2 2 0 012 2v4"/><circle cx="18" cy="18" r="4"/><path d="M15 3v4"/><path d="M7 3v4"/><path d="M3 11h16"/><path d="M18 16.496V18l1 1"/></svg><time class=article-time--published>Oct 25, 2018</time></div><div><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><circle cx="12" cy="12" r="9"/><polyline points="12 7 12 12 15 15"/></svg><time class=article-time--reading>5 minute read</time></div></footer></div></header><section class=article-content><h1 id=问题引入>问题引入</h1><p>给定 $64$ 位有符号整数 $a,b,m$ （类型为 <code>int64_t</code>），希望求出 $a\times b \bmod m$ 的数值。</p><div class=highlight><pre class=chroma><code class=language-c data-lang=c><span class=kt>int64_t</span> <span class=nf>multimod</span><span class=p>(</span><span class=kt>int64_t</span> <span class=n>a</span><span class=p>,</span> <span class=kt>int64_t</span> <span class=n>b</span><span class=p>,</span> <span class=kt>int64_t</span> <span class=n>m</span><span class=p>);</span>
</code></pre></div><p>给出一个尽可能高效的正确 <code>multimod</code> 实现。使得它对于任意在 $[0,2^{63}-1]$ 范围内的 $a,b,m$ 均能正确求出 $a\times b \bmod m$ 的数值，且在任何时候不触发有符号整数溢出。</p><h1 id=解决方法>解决方法</h1><h2 id=运行环境>运行环境</h2><p>Windows 10 （64 位） 上 Hyper-V 平台，Debian 9 虚拟机 （64 位）</p><ul><li>CPU 型号：Intel(R) Core(TM) i7-7700HQ</li><li>CPU 主频：2.80 GHz</li></ul><h2 id=基础设施>基础设施</h2><p>为使实验顺利，实验前先准备了测试程序和时间测量程序。</p><h3 id=测试程序>测试程序</h3><p>使用 Python 自动生成测试用例，运行程序，检查输出。</p><div class=highlight><pre class=chroma><code class=language-python data-lang=python><span class=kn>import</span> <span class=nn>os</span>
<span class=kn>import</span> <span class=nn>random</span>
<span class=kn>import</span> <span class=nn>sys</span>

<span class=k>def</span> <span class=nf>getNum</span><span class=p>():</span>
    <span class=k>return</span> <span class=n>random</span><span class=o>.</span><span class=n>randint</span><span class=p>(</span><span class=mi>0</span><span class=p>,</span><span class=mi>2</span><span class=o>**</span><span class=mi>63</span><span class=o>-</span><span class=mi>1</span><span class=p>)</span>

<span class=k>if</span> <span class=vm>__name__</span><span class=o>==</span><span class=s2>&#34;__main__&#34;</span><span class=p>:</span>
    <span class=n>cnt</span> <span class=o>=</span> <span class=mi>10</span><span class=o>**</span><span class=mi>4</span><span class=p>;</span>
    <span class=n>passed</span> <span class=o>=</span> <span class=mi>0</span>
    <span class=n>failed</span> <span class=o>=</span> <span class=mi>0</span>
    <span class=k>if</span> <span class=nb>len</span><span class=p>(</span><span class=n>sys</span><span class=o>.</span><span class=n>argv</span><span class=p>)</span><span class=o>&gt;</span><span class=mi>1</span><span class=p>:</span>
        <span class=n>cnt</span> <span class=o>=</span> <span class=nb>int</span><span class=p>(</span><span class=n>sys</span><span class=o>.</span><span class=n>argv</span><span class=p>[</span><span class=mi>1</span><span class=p>])</span>
    <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Running&#34;</span><span class=p>)</span>
    <span class=k>for</span> <span class=n>i</span> <span class=ow>in</span> <span class=nb>range</span><span class=p>(</span><span class=n>cnt</span><span class=p>):</span>
        <span class=n>a</span><span class=p>,</span><span class=n>b</span><span class=p>,</span><span class=n>m</span> <span class=o>=</span> <span class=n>getNum</span><span class=p>(),</span><span class=n>getNum</span><span class=p>(),</span><span class=n>getNum</span><span class=p>()</span>
        <span class=n>ans</span> <span class=o>=</span> <span class=n>a</span><span class=o>*</span><span class=n>b</span><span class=o>%</span><span class=n>m</span>
        <span class=n>_ans</span> <span class=o>=</span> <span class=nb>int</span><span class=p>(</span><span class=n>os</span><span class=o>.</span><span class=n>popen</span><span class=p>(</span><span class=s2>&#34; &#34;</span><span class=o>.</span><span class=n>join</span><span class=p>([</span><span class=s2>&#34;./runner&#34;</span><span class=p>,</span><span class=nb>str</span><span class=p>(</span><span class=n>a</span><span class=p>),</span><span class=nb>str</span><span class=p>(</span><span class=n>b</span><span class=p>),</span><span class=nb>str</span><span class=p>(</span><span class=n>m</span><span class=p>)]))</span><span class=o>.</span><span class=n>read</span><span class=p>())</span>
        <span class=k>if</span> <span class=n>ans</span> <span class=o>!=</span> <span class=n>_ans</span><span class=p>:</span>
            <span class=k>if</span> <span class=n>failed</span> <span class=o>&lt;=</span> <span class=mi>5</span><span class=p>:</span>
                <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Error for a =&#34;</span><span class=p>,</span><span class=n>a</span><span class=p>,</span><span class=s2>&#34;b =&#34;</span><span class=p>,</span><span class=n>b</span><span class=p>,</span><span class=s2>&#34;m =&#34;</span><span class=p>,</span><span class=n>m</span><span class=p>,</span><span class=s2>&#34;:&#34;</span><span class=p>)</span>
                <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;expected&#34;</span><span class=p>,</span><span class=n>ans</span><span class=p>,</span><span class=s2>&#34;but real&#34;</span><span class=p>,</span><span class=n>_ans</span><span class=p>)</span>
            <span class=n>failed</span><span class=o>+=</span><span class=mi>1</span>
        <span class=k>else</span><span class=p>:</span>
            <span class=n>passed</span><span class=o>+=</span><span class=mi>1</span>
    <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Test&#34;</span><span class=p>,</span><span class=n>cnt</span><span class=p>,</span><span class=s2>&#34;cases&#34;</span><span class=p>);</span>
    <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Passed&#34;</span><span class=p>,</span><span class=n>passed</span><span class=p>);</span>
    <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Failed&#34;</span><span class=p>,</span><span class=n>failed</span><span class=p>);</span>
</code></pre></div><p>其中 <code>runner</code> 程序调用 <code>multimod</code> 并将结果输出。</p><div class=highlight><pre class=chroma><code class=language-c data-lang=c><span class=cp>#include</span> <span class=cpf>&lt;stdint.h&gt;</span><span class=cp>
</span><span class=cp>#include</span> <span class=cpf>&lt;assert.h&gt;</span><span class=cp>
</span><span class=cp>#include</span> <span class=cpf>&lt;string.h&gt;</span><span class=cp>
</span><span class=cp>#include</span> <span class=cpf>&lt;stdio.h&gt;</span><span class=cp>
</span><span class=cp>#include</span> <span class=cpf>&#34;p.c&#34;</span><span class=cp>
</span><span class=cp></span>
<span class=k>typedef</span> <span class=nf>int64_t</span> <span class=p>(</span><span class=o>*</span><span class=n>func</span><span class=p>)(</span><span class=kt>int64_t</span><span class=p>,</span> <span class=kt>int64_t</span><span class=p>,</span> <span class=kt>int64_t</span><span class=p>);</span>

<span class=kt>int</span> <span class=nf>main</span><span class=p>(</span><span class=kt>int</span> <span class=n>argc</span><span class=p>,</span> <span class=kt>char</span> <span class=o>*</span><span class=n>argv</span><span class=p>[]){</span>
    <span class=n>assert</span><span class=p>(</span><span class=n>argc</span> <span class=o>==</span> <span class=mi>4</span><span class=p>);</span>
    <span class=kt>int64_t</span> <span class=n>a</span><span class=p>,</span> <span class=n>b</span><span class=p>,</span> <span class=n>m</span><span class=p>;</span>
    <span class=n>sscanf</span><span class=p>(</span><span class=n>argv</span><span class=p>[</span><span class=mi>1</span><span class=p>],</span> <span class=s>&#34;%lld&#34;</span><span class=p>,</span> <span class=o>&amp;</span><span class=n>a</span><span class=p>);</span>
    <span class=n>sscanf</span><span class=p>(</span><span class=n>argv</span><span class=p>[</span><span class=mi>2</span><span class=p>],</span> <span class=s>&#34;%lld&#34;</span><span class=p>,</span> <span class=o>&amp;</span><span class=n>b</span><span class=p>);</span>
    <span class=n>sscanf</span><span class=p>(</span><span class=n>argv</span><span class=p>[</span><span class=mi>3</span><span class=p>],</span> <span class=s>&#34;%lld&#34;</span><span class=p>,</span> <span class=o>&amp;</span><span class=n>m</span><span class=p>);</span>
    <span class=n>func</span> <span class=n>f</span> <span class=o>=</span> <span class=n>multimod</span><span class=p>;</span>
    <span class=kt>int64_t</span> <span class=n>ans</span> <span class=o>=</span> <span class=n>f</span><span class=p>(</span><span class=n>a</span><span class=p>,</span> <span class=n>b</span><span class=p>,</span> <span class=n>m</span><span class=p>);</span>
    <span class=n>printf</span><span class=p>(</span><span class=s>&#34;%lld</span><span class=se>\n</span><span class=s>&#34;</span><span class=p>,</span><span class=n>ans</span><span class=p>);</span>
    <span class=k>return</span> <span class=mi>0</span><span class=p>;</span>
<span class=p>}</span>
</code></pre></div><h3 id=计时程序>计时程序</h3><p>使用 Python 随机生成测试用例，调用计时程序得到单次运行时间，统计后取平均值，会输出总耗时，平均耗时，和最大耗时，最小耗时。</p><div class=highlight><pre class=chroma><code class=language-python data-lang=python><span class=kn>import</span> <span class=nn>os</span>
<span class=kn>import</span> <span class=nn>random</span>
<span class=kn>import</span> <span class=nn>sys</span>
<span class=kn>import</span> <span class=nn>time</span>

<span class=k>def</span> <span class=nf>getNum</span><span class=p>():</span>
    <span class=k>return</span> <span class=n>random</span><span class=o>.</span><span class=n>randint</span><span class=p>(</span><span class=mi>0</span><span class=p>,</span><span class=mi>2</span><span class=o>**</span><span class=mi>63</span><span class=o>-</span><span class=mi>1</span><span class=p>)</span>

<span class=k>if</span> <span class=vm>__name__</span><span class=o>==</span><span class=s2>&#34;__main__&#34;</span><span class=p>:</span>
    <span class=n>cnt</span> <span class=o>=</span> <span class=mi>10</span><span class=o>**</span><span class=mi>4</span><span class=p>;</span>
    <span class=n>passed</span> <span class=o>=</span> <span class=mi>0</span>
    <span class=n>failed</span> <span class=o>=</span> <span class=mi>0</span>
    <span class=k>if</span> <span class=nb>len</span><span class=p>(</span><span class=n>sys</span><span class=o>.</span><span class=n>argv</span><span class=p>)</span><span class=o>&gt;</span><span class=mi>1</span><span class=p>:</span>
        <span class=n>cnt</span> <span class=o>=</span> <span class=nb>int</span><span class=p>(</span><span class=n>sys</span><span class=o>.</span><span class=n>argv</span><span class=p>[</span><span class=mi>1</span><span class=p>])</span>
    <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Running&#34;</span><span class=p>)</span>
    <span class=n>start</span> <span class=o>=</span> <span class=n>time</span><span class=o>.</span><span class=n>time</span><span class=p>()</span>
    <span class=n>l</span> <span class=o>=</span> <span class=p>[]</span>
    <span class=k>for</span> <span class=n>i</span> <span class=ow>in</span> <span class=nb>range</span><span class=p>(</span><span class=n>cnt</span><span class=p>):</span>
        <span class=n>a</span><span class=p>,</span><span class=n>b</span><span class=p>,</span><span class=n>m</span> <span class=o>=</span> <span class=n>getNum</span><span class=p>(),</span><span class=n>getNum</span><span class=p>(),</span><span class=n>getNum</span><span class=p>()</span>
        <span class=n>ans</span> <span class=o>=</span> <span class=nb>int</span><span class=p>(</span><span class=n>os</span><span class=o>.</span><span class=n>popen</span><span class=p>(</span><span class=s2>&#34; &#34;</span><span class=o>.</span><span class=n>join</span><span class=p>([</span><span class=s2>&#34;./timer&#34;</span><span class=p>,</span><span class=nb>str</span><span class=p>(</span><span class=n>a</span><span class=p>),</span><span class=nb>str</span><span class=p>(</span><span class=n>b</span><span class=p>),</span><span class=nb>str</span><span class=p>(</span><span class=n>m</span><span class=p>)]))</span><span class=o>.</span><span class=n>read</span><span class=p>())</span>
        <span class=n>l</span><span class=o>.</span><span class=n>append</span><span class=p>((</span><span class=n>a</span><span class=p>,</span><span class=n>b</span><span class=p>,</span><span class=n>m</span><span class=p>,</span><span class=n>ans</span><span class=p>))</span>
    <span class=n>end</span> <span class=o>=</span> <span class=n>time</span><span class=o>.</span><span class=n>time</span><span class=p>()</span>
    <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Test&#34;</span><span class=p>,</span><span class=n>cnt</span><span class=p>,</span><span class=s2>&#34;cases use&#34;</span><span class=p>,</span><span class=n>end</span><span class=o>-</span><span class=n>start</span><span class=p>,</span><span class=s2>&#34;seconds&#34;</span><span class=p>);</span>
    <span class=n>_l</span> <span class=o>=</span> <span class=nb>list</span><span class=p>(</span><span class=nb>map</span><span class=p>(</span><span class=k>lambda</span> <span class=n>x</span><span class=p>:</span> <span class=n>x</span><span class=p>[</span><span class=mi>3</span><span class=p>],</span><span class=n>l</span><span class=p>))</span>
    <span class=n>sumC</span> <span class=o>=</span> <span class=nb>sum</span><span class=p>(</span><span class=n>_l</span><span class=p>)</span>
    <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Sum CPU cycles:&#34;</span><span class=p>,</span><span class=n>sumC</span><span class=p>)</span>
    <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Average CPU cycles:&#34;</span><span class=p>,</span><span class=n>sumC</span> <span class=o>/</span> <span class=nb>len</span><span class=p>(</span><span class=n>l</span><span class=p>))</span>
    <span class=n>mx</span><span class=p>,</span><span class=n>mn</span> <span class=o>=</span> <span class=nb>max</span><span class=p>(</span><span class=n>_l</span><span class=p>),</span><span class=nb>min</span><span class=p>(</span><span class=n>_l</span><span class=p>)</span>
    <span class=n>idmx</span><span class=p>,</span><span class=n>idmn</span> <span class=o>=</span> <span class=n>_l</span><span class=o>.</span><span class=n>index</span><span class=p>(</span><span class=n>mx</span><span class=p>),</span><span class=n>_l</span><span class=o>.</span><span class=n>index</span><span class=p>(</span><span class=n>mn</span><span class=p>)</span>
    <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Maximum:&#34;</span><span class=p>,</span> <span class=n>mx</span><span class=p>,</span> <span class=s2>&#34;@&#34;</span><span class=p>,</span> <span class=n>l</span><span class=p>[</span><span class=n>idmx</span><span class=p>])</span>
    <span class=nb>print</span><span class=p>(</span><span class=s2>&#34;Minimum:&#34;</span><span class=p>,</span> <span class=n>mn</span><span class=p>,</span> <span class=s2>&#34;@&#34;</span><span class=p>,</span> <span class=n>l</span><span class=p>[</span><span class=n>idmn</span><span class=p>])</span>
</code></pre></div><p>其中 <code>timer</code> 程序调用 <code>multimod</code> 进行运算并使用 Linux 中的 <code>clock_gettime</code> 函数获取执行时间（纳秒级，CPU 时钟数）。</p><div class=highlight><pre class=chroma><code class=language-c data-lang=c><span class=cp>#include</span> <span class=cpf>&lt;stdint.h&gt;</span><span class=cp>
</span><span class=cp>#include</span> <span class=cpf>&lt;assert.h&gt;</span><span class=cp>
</span><span class=cp>#include</span> <span class=cpf>&lt;stdio.h&gt;</span><span class=cp>
</span><span class=cp>#include</span> <span class=cpf>&lt;time.h&gt;</span><span class=cp>
</span><span class=cp></span>
<span class=cp>#include</span> <span class=cpf>&#34;p.c&#34;</span><span class=cp>
</span><span class=cp></span>
<span class=k>typedef</span> <span class=nf>int64_t</span> <span class=p>(</span><span class=o>*</span><span class=n>func</span><span class=p>)(</span><span class=kt>int64_t</span><span class=p>,</span> <span class=kt>int64_t</span><span class=p>,</span> <span class=kt>int64_t</span><span class=p>);</span>
<span class=k>volatile</span> <span class=kt>int64_t</span> <span class=n>a</span><span class=p>,</span> <span class=n>b</span><span class=p>,</span> <span class=n>m</span><span class=p>;</span>
<span class=kt>uint64_t</span> <span class=nf>measure</span><span class=p>(</span><span class=n>func</span> <span class=n>f</span><span class=p>){</span>
    <span class=k>struct</span> <span class=n>timespec</span> <span class=n>st</span><span class=p>;</span>
    <span class=n>clock_gettime</span><span class=p>(</span><span class=n>CLOCK_MONOTONIC</span><span class=p>,</span><span class=o>&amp;</span><span class=n>st</span><span class=p>);</span>
    <span class=kt>int64_t</span> <span class=n>before</span> <span class=o>=</span> <span class=n>st</span><span class=p>.</span><span class=n>tv_nsec</span><span class=p>;</span>
    <span class=n>f</span><span class=p>(</span><span class=n>a</span><span class=p>,</span> <span class=n>b</span><span class=p>,</span> <span class=n>m</span><span class=p>);</span>
    <span class=n>clock_gettime</span><span class=p>(</span><span class=n>CLOCK_MONOTONIC</span><span class=p>,</span><span class=o>&amp;</span><span class=n>st</span><span class=p>);</span>
    <span class=kt>int64_t</span> <span class=n>after</span> <span class=o>=</span> <span class=n>st</span><span class=p>.</span><span class=n>tv_nsec</span><span class=p>;</span>
    <span class=k>return</span> <span class=n>after</span> <span class=o>-</span> <span class=n>before</span><span class=p>;</span>
<span class=p>}</span>

<span class=kt>int</span> <span class=nf>main</span><span class=p>(</span><span class=kt>int</span> <span class=n>argc</span><span class=p>,</span> <span class=kt>char</span> <span class=o>*</span><span class=n>argv</span><span class=p>[]){</span>
    <span class=n>assert</span><span class=p>(</span><span class=n>argc</span> <span class=o>==</span> <span class=mi>4</span><span class=p>);</span>
    <span class=n>sscanf</span><span class=p>(</span><span class=n>argv</span><span class=p>[</span><span class=mi>1</span><span class=p>],</span> <span class=s>&#34;%lld&#34;</span><span class=p>,</span> <span class=o>&amp;</span><span class=n>a</span><span class=p>);</span>
    <span class=n>sscanf</span><span class=p>(</span><span class=n>argv</span><span class=p>[</span><span class=mi>2</span><span class=p>],</span> <span class=s>&#34;%lld&#34;</span><span class=p>,</span> <span class=o>&amp;</span><span class=n>b</span><span class=p>);</span>
    <span class=n>sscanf</span><span class=p>(</span><span class=n>argv</span><span class=p>[</span><span class=mi>3</span><span class=p>],</span> <span class=s>&#34;%lld&#34;</span><span class=p>,</span> <span class=o>&amp;</span><span class=n>m</span><span class=p>);</span>
    <span class=n>func</span> <span class=n>f</span> <span class=o>=</span> <span class=n>multimod</span><span class=p>;</span>
    <span class=kt>uint64_t</span> <span class=n>ans</span> <span class=o>=</span> <span class=n>measure</span><span class=p>(</span><span class=n>f</span><span class=p>);</span>
    <span class=n>printf</span><span class=p>(</span><span class=s>&#34;%llu</span><span class=se>\n</span><span class=s>&#34;</span><span class=p>,</span><span class=n>ans</span><span class=p>);</span>
    <span class=k>return</span> <span class=mi>0</span><span class=p>;</span>
<span class=p>}</span>
</code></pre></div><h3 id=makefile>Makefile</h3><p>Makefile 文件指定依赖关系，使用 <code>make check</code> 和 <code>make time</code> 调用上述程序。</p><div class=highlight><pre class=chroma><code class=language-makefile data-lang=makefile><span class=nf>.PHONY </span><span class=o>:</span> <span class=n>clean</span> <span class=n>time</span> <span class=n>check</span> <span class=n>all</span>

<span class=nf>all </span><span class=o>:</span> <span class=n>timer</span> <span class=n>runner</span>
	@echo <span class=s2>&#34;Builded&#34;</span>

<span class=c># p.o : p.c
</span><span class=c></span>	<span class=c1># $(CC) p.c -c $(CFLAGS) -o p.o</span>

<span class=nf>timer</span><span class=o>:</span> <span class=n>timer</span>.<span class=n>o</span> <span class=n>p</span>.<span class=n>c</span>
	<span class=k>$(</span>CC<span class=k>)</span> -o timer timer.o <span class=k>$(</span>CFLAGS<span class=k>)</span> <span class=k>$(</span>LDFLAGS<span class=k>)</span> -O2

<span class=nf>runner</span><span class=o>:</span> <span class=n>runner</span>.<span class=n>o</span> <span class=n>p</span>.<span class=n>c</span>
	<span class=k>$(</span>CC<span class=k>)</span> -o runner runner.o <span class=k>$(</span>CFLAGS<span class=k>)</span> <span class=k>$(</span>LDFLAGS<span class=k>)</span> -O2

<span class=nf>time</span><span class=o>:</span> <span class=n>timer</span>
	@python3 ./measure.py

<span class=nf>check</span><span class=o>:</span> <span class=n>runner</span>
	@python3 ./checker.py

<span class=nf>clean</span><span class=o>:</span>
	-rm -f *.o
</code></pre></div><p>有了上述基础设施后，下面开始编写 <code>multimod</code> 函数。</p><h2 id=基准实现>基准实现</h2><p>使用朴素二进制乘法，设输入 $A,B$，则结果 $C$ 有</p><p>$$C_{i+j} = \sum_{0\le i,j &lt; 64} A_iB_j$$</p><p>则有</p><p>$$Ans=(\sum_{0\le i &lt; 128} (C_i\times 2^i)\bmod m)\bmod m$$</p><p>注意到 $0\le m &lt; 2^{63}$，两个 $m$ 以内的数相加不会发生无符号溢出。故转成无符号数，将乘 $2^i$，转化为 $i$ 次翻倍迭代取模就可以避免溢出。</p><p>最终程序为：</p><div class=highlight><pre class=chroma><code class=language-c data-lang=c><span class=cp>#include</span> <span class=cpf>&lt;stdint.h&gt;</span><span class=cp>
</span><span class=cp></span><span class=kt>int64_t</span> <span class=nf>multimod</span><span class=p>(</span><span class=kt>int64_t</span> <span class=n>a</span><span class=p>,</span> <span class=kt>int64_t</span> <span class=n>b</span><span class=p>,</span> <span class=kt>int64_t</span> <span class=n>m</span><span class=p>){</span>
    <span class=k>const</span> <span class=kt>int</span> <span class=n>L</span> <span class=o>=</span> <span class=mi>128</span><span class=p>;</span>
    <span class=kt>uint64_t</span> <span class=n>c</span><span class=p>[</span><span class=n>L</span><span class=p>];</span>
    <span class=k>for</span><span class=p>(</span><span class=kt>int</span> <span class=n>i</span> <span class=o>=</span> <span class=mi>0</span><span class=p>;</span> <span class=n>i</span> <span class=o>&lt;</span> <span class=n>L</span><span class=p>;</span> <span class=n>i</span><span class=o>++</span><span class=p>)</span>
        <span class=n>c</span><span class=p>[</span><span class=n>i</span><span class=p>]</span> <span class=o>=</span> <span class=mi>0</span><span class=p>;</span>
    <span class=k>for</span><span class=p>(</span><span class=kt>int</span> <span class=n>i</span> <span class=o>=</span> <span class=mi>0</span><span class=p>;</span> <span class=n>i</span> <span class=o>&lt;</span> <span class=mi>64</span><span class=p>;</span> <span class=n>i</span><span class=o>++</span><span class=p>)</span>
        <span class=k>for</span><span class=p>(</span><span class=kt>int</span> <span class=n>j</span> <span class=o>=</span> <span class=mi>0</span><span class=p>;</span> <span class=n>j</span> <span class=o>&lt;</span> <span class=mi>64</span><span class=p>;</span> <span class=n>j</span><span class=o>++</span><span class=p>)</span>
            <span class=n>c</span><span class=p>[</span><span class=n>i</span><span class=o>+</span><span class=n>j</span><span class=p>]</span><span class=o>+=</span><span class=p>((</span><span class=n>a</span><span class=o>&gt;&gt;</span><span class=n>i</span><span class=o>&amp;</span><span class=mi>1</span><span class=p>)</span><span class=o>&amp;</span><span class=p>(</span><span class=n>b</span><span class=o>&gt;&gt;</span><span class=n>j</span><span class=o>&amp;</span><span class=mi>1</span><span class=p>));</span>
    <span class=kt>uint64_t</span> <span class=n>ans</span> <span class=o>=</span> <span class=mi>0</span><span class=p>;</span>
    <span class=k>for</span><span class=p>(</span><span class=kt>int</span> <span class=n>i</span><span class=o>=</span><span class=mi>0</span><span class=p>;</span><span class=n>i</span><span class=o>&lt;</span><span class=n>L</span><span class=p>;</span><span class=n>i</span><span class=o>++</span><span class=p>){</span>
        <span class=kt>uint64_t</span> <span class=n>t</span> <span class=o>=</span> <span class=n>c</span><span class=p>[</span><span class=n>i</span><span class=p>];</span>
        <span class=k>for</span><span class=p>(</span><span class=kt>int</span> <span class=n>j</span><span class=o>=</span><span class=mi>0</span><span class=p>;</span><span class=n>j</span><span class=o>&lt;</span><span class=n>i</span><span class=p>;</span><span class=n>j</span><span class=o>++</span><span class=p>)</span>
            <span class=n>t</span><span class=o>=</span><span class=p>(</span><span class=n>t</span><span class=o>&lt;&lt;</span><span class=mi>1</span><span class=p>)</span><span class=o>%</span><span class=n>m</span><span class=p>;</span>
        <span class=n>ans</span><span class=o>=</span><span class=p>(</span><span class=n>ans</span><span class=o>+</span><span class=n>t</span><span class=p>)</span><span class=o>%</span><span class=n>m</span><span class=p>;</span>
    <span class=p>}</span>
    <span class=k>return</span> <span class=n>ans</span><span class=p>;</span>
<span class=p>}</span>
</code></pre></div><p>使用 <code>make check</code> 测试，输出如下：</p><pre><code>Running
Test 10000 cases
Passed 10000
Failed 0
</code></pre><p>通过测试。</p><h2 id=性能优化>性能优化</h2><h3 id=优化1二进制拆分>优化1：二进制拆分</h3><p>使用 ACM/ICPC 圈子中常用的一种计算 $ab \bmod m$ 的算法。将 $b$ 二进制拆分，得到其二进制表示 $(b_{63}\dots b_0)_2$，则</p><p>$$
ab=\sum_{0\le i&lt;64} b_i\times a2^i
$$</p><p>$a2^i$ 可以递推得到，由此可得到 $O(\log b)$ 的算法。类似基准实现中讨论，转成无符号数后不会出现溢出问题。</p><div class=highlight><pre class=chroma><code class=language-c data-lang=c><span class=cp>#include</span> <span class=cpf>&lt;stdint.h&gt;</span><span class=cp>
</span><span class=cp></span><span class=kt>int64_t</span> <span class=nf>multimod</span><span class=p>(</span><span class=kt>int64_t</span> <span class=n>a</span><span class=p>,</span> <span class=kt>int64_t</span> <span class=n>b</span><span class=p>,</span> <span class=kt>int64_t</span> <span class=n>m</span><span class=p>){</span>
    <span class=kt>uint64_t</span> <span class=n>_a</span> <span class=o>=</span> <span class=n>a</span> <span class=o>%</span> <span class=n>m</span><span class=p>,</span> <span class=n>_b</span> <span class=o>=</span> <span class=n>b</span> <span class=o>%</span> <span class=n>m</span><span class=p>;</span>
    <span class=kt>uint64_t</span> <span class=n>ans</span> <span class=o>=</span> <span class=mi>0</span><span class=p>;</span>
    <span class=k>while</span><span class=p>(</span><span class=n>_b</span><span class=p>){</span>
        <span class=k>if</span><span class=p>(</span><span class=n>_b</span> <span class=o>&amp;</span> <span class=mi>1</span><span class=p>){</span>
            <span class=n>ans</span><span class=o>+=</span><span class=n>_a</span><span class=p>;</span>
            <span class=n>ans</span><span class=o>%=</span><span class=n>m</span><span class=p>;</span>
        <span class=p>}</span>
        <span class=n>_a</span><span class=o>+=</span><span class=n>_a</span><span class=p>;</span>
        <span class=n>_a</span><span class=o>%=</span><span class=n>m</span><span class=p>;</span>
        <span class=n>_b</span><span class=o>&gt;&gt;=</span><span class=mi>1</span><span class=p>;</span>
    <span class=p>}</span>
    <span class=k>return</span> <span class=n>ans</span><span class=p>;</span>
<span class=p>}</span>
</code></pre></div><p>使用 <code>make check</code> 测试，输出如下：</p><pre><code>Running
Test 10000 cases
Passed 10000
Failed 0
</code></pre><p>通过测试。</p><h3 id=优化2高低位分别处理>优化2：高低位分别处理</h3><p>类比计算 32 位整数乘积时的算法。将 $a,b$ 的高32位，和低32位各自取出，得到</p><p>$$a=a_1\times 2^{32} + a_0$$
$$b=b_1\times 2^{32} + b_0$$</p><p>则</p><p>$$
\begin{aligned}
ab&=(a_1\times 2^{32} + a_0)(b_1\times 2^{32} + b_0)\<br>&=a_1b_1\times 2^{64} + (a_0b_1+a_1b_0)\times 2^{32} + a_0b_0
\end{aligned}
$$</p><p>由输入范围限制，可得 $a_1b_1&lt;2^{64},a_0b_1+a_1b_0&lt;2^{64}$，但 $a_0b_0$ 可能发生一位溢出（因为 $a_0,b_0$ 可能等于 $2^{32}-1$。</p><p>设 $ab=c=c_1\times 2^{64} + c_0$，则有</p><p>$$c_1 = a_1b_1+(a_0b_1+a_1b_0)_ {h32} + \text{OF}(a_0b_0)$$
$$c_0 = (a_0b_0)\bmod 2^{32}+(a_0b_1+a_1b_0)_{l32}$$</p><p>由此可计算得出 $c_1,c_0$，由基准实现中讨论，将 $c_1\times 2^{64} \bmod m$ 转化成 $64$ 次翻倍迭代，避免溢出问题。</p><div class=highlight><pre class=chroma><code class=language-c data-lang=c><span class=cp>#include</span> <span class=cpf>&lt;stdint.h&gt;</span><span class=cp>
</span><span class=cp></span><span class=c1>// #include &lt;assert.h&gt;
</span><span class=c1></span><span class=k>static</span> <span class=kt>uint32_t</span> <span class=n>_32f</span> <span class=o>=</span> <span class=p>(</span><span class=o>~</span><span class=p>((</span><span class=kt>uint32_t</span><span class=p>)</span><span class=mi>0</span><span class=p>));</span>
<span class=k>static</span> <span class=kt>uint64_t</span> <span class=n>_64f</span> <span class=o>=</span> <span class=p>(</span><span class=o>~</span><span class=p>((</span><span class=kt>uint64_t</span><span class=p>)</span><span class=mi>0</span><span class=p>));</span>
<span class=kt>int64_t</span> <span class=nf>multimod</span><span class=p>(</span><span class=kt>int64_t</span> <span class=n>a</span><span class=p>,</span> <span class=kt>int64_t</span> <span class=n>b</span><span class=p>,</span> <span class=kt>int64_t</span> <span class=n>m</span><span class=p>){</span>
    <span class=kt>uint64_t</span> <span class=n>a1</span> <span class=o>=</span> <span class=n>a</span><span class=o>&gt;&gt;</span><span class=mi>32</span><span class=p>,</span> <span class=n>a0</span> <span class=o>=</span> <span class=n>a</span><span class=o>&amp;</span><span class=n>_32f</span><span class=p>;</span>
    <span class=kt>uint64_t</span> <span class=n>b1</span> <span class=o>=</span> <span class=n>b</span><span class=o>&gt;&gt;</span><span class=mi>32</span><span class=p>,</span> <span class=n>b0</span> <span class=o>=</span> <span class=n>b</span><span class=o>&amp;</span><span class=n>_32f</span><span class=p>;</span>
    <span class=kt>uint64_t</span> <span class=n>t</span> <span class=o>=</span> <span class=n>a1</span><span class=o>*</span><span class=n>b0</span> <span class=o>+</span> <span class=n>a0</span><span class=o>*</span><span class=n>b1</span><span class=p>;</span>
    <span class=kt>uint64_t</span> <span class=n>t1</span> <span class=o>=</span> <span class=n>t</span><span class=o>&gt;&gt;</span><span class=mi>32</span><span class=p>,</span> <span class=n>t0</span> <span class=o>=</span> <span class=n>t</span><span class=o>&amp;</span><span class=n>_32f</span><span class=p>,</span> <span class=n>tc0</span> <span class=o>=</span> <span class=n>a0</span><span class=o>*</span><span class=n>b0</span><span class=p>;</span>
    <span class=kt>uint64_t</span> <span class=n>c1</span> <span class=o>=</span> <span class=n>a1</span><span class=o>*</span><span class=n>b1</span> <span class=o>+</span> <span class=n>t1</span><span class=p>,</span> <span class=n>c0</span> <span class=o>=</span> <span class=n>tc0</span> <span class=o>+</span> <span class=p>(</span><span class=n>t0</span><span class=o>&lt;&lt;</span><span class=mi>32</span><span class=p>);</span>
    <span class=k>if</span><span class=p>(</span><span class=n>c0</span><span class=o>&lt;</span><span class=n>tc0</span><span class=p>)</span> <span class=c1>// overflow
</span><span class=c1></span>        <span class=n>c1</span><span class=o>++</span><span class=p>;</span>
    <span class=c1>// __int128 _cor = ((__int128)a)*((__int128)b);
</span><span class=c1></span>    <span class=c1>// assert((_cor&gt;&gt;64)==c1);
</span><span class=c1></span>    <span class=c1>// assert((_cor&amp;_64f)==c0);
</span><span class=c1></span>    <span class=k>for</span><span class=p>(</span><span class=kt>int</span> <span class=n>i</span><span class=o>=</span><span class=mi>0</span><span class=p>;</span><span class=n>i</span><span class=o>&lt;</span><span class=mi>64</span><span class=p>;</span><span class=n>i</span><span class=o>++</span><span class=p>)</span>
        <span class=n>c1</span> <span class=o>=</span> <span class=p>(</span><span class=n>c1</span><span class=o>&lt;&lt;</span><span class=mi>1</span><span class=p>)</span><span class=o>%</span><span class=n>m</span><span class=p>;</span>
    <span class=k>return</span> <span class=p>(</span><span class=n>c0</span><span class=o>%</span><span class=n>m</span> <span class=o>+</span> <span class=n>c1</span><span class=p>)</span><span class=o>%</span><span class=n>m</span><span class=p>;</span>
<span class=p>}</span>
</code></pre></div><p>使用 <code>make check</code> 测试，输出如下：</p><pre><code>Running
Test 10000 cases
Passed 10000
Failed 0
</code></pre><p>通过测试。</p><h3 id=效率实测>效率实测</h3><p>使用 <code>make time</code> 测试得到。以下表格中数值为测试 10000 组随机用例，得到的平均单次操作 CPU 时钟数。</p><table><thead><tr><th>程序</th><th><code>O0</code></th><th><code>O1</code></th><th><code>O2</code></th></tr></thead><tbody><tr><td><code>p1.c</code></td><td>$98554.87$</td><td>$102880.89$</td><td>$100160.11$</td></tr><tr><td><code>p2.c</code></td><td>$1470.79$</td><td>$1472.98$</td><td>$1473.57$</td></tr><tr><td><code>p3.c</code></td><td>$1185.46$</td><td>$1217.1$</td><td>$1207.91$</td></tr></tbody></table><p>可见优化 1，2 较基准实现提高显著，不同编译优化级别对此程序运行效率影响不大。</p><p>注：<code>make time</code> 输出内容</p><div class=highlight><pre class=chroma><code class=language-sh data-lang=sh><span class=c1># -O0</span>

<span class=c1># p1.c</span>

Running
Test <span class=m>10000</span> cases use 11.16751217842102 seconds
Sum CPU cycles: <span class=m>985548700</span>
Average CPU cycles: 98554.87
Maximum: <span class=m>4802300</span> @ <span class=o>(</span>2265130052289059763, 7783645480371944058, 3115603639858794422, 4802300<span class=o>)</span>
Minimum: <span class=m>87600</span> @ <span class=o>(</span>20906801206135418, 1235445072834323451, 7495840395140955697, 87600<span class=o>)</span>

<span class=c1># p2.c</span>

Running
Test <span class=m>10000</span> cases use 11.892813444137573 seconds
Sum CPU cycles: <span class=m>14707900</span>
Average CPU cycles: 1470.79
Maximum: <span class=m>142700</span> @ <span class=o>(</span>1598719057711499987, 8349967337302892367, 5320637895082198498, 142700<span class=o>)</span>
Minimum: <span class=m>1000</span> @ <span class=o>(</span>7326329361318569666, 6606926909931228833, 6606926867070148477, 1000<span class=o>)</span>

<span class=c1># p3.c</span>

Running
Test <span class=m>10000</span> cases use 12.87213659286499 seconds
Sum CPU cycles: <span class=m>11854600</span>
Average CPU cycles: 1185.46
Maximum: <span class=m>58500</span> @ <span class=o>(</span>957615596508775045, 4417329977803451093, 6085566768103491103, 58500<span class=o>)</span>
Minimum: <span class=m>900</span> @ <span class=o>(</span>3868418006544775637, 3115279496994464447, 2343316703378067646, 900<span class=o>)</span>

<span class=c1># -O1</span>

<span class=c1># p1.c</span>

Running
Test <span class=m>10000</span> cases use 12.523572444915771 seconds
Sum CPU cycles: <span class=m>1028808900</span>
Average CPU cycles: 102880.89
Maximum: <span class=m>1932400</span> @ <span class=o>(</span>7242145147389599538, 1833121011939475515, 6206342766087253890, 1932400<span class=o>)</span>
Minimum: <span class=m>87500</span> @ <span class=o>(</span>1822799065865324744, 2537174733001160, 158801504793342122, 87500<span class=o>)</span>

<span class=c1># p2.c</span>

Running
Test <span class=m>10000</span> cases use 10.98656439781189 seconds
Sum CPU cycles: <span class=m>14729800</span>
Average CPU cycles: 1472.98
Maximum: <span class=m>75600</span> @ <span class=o>(</span>221577760594163762, 3833386045247446405, 2751795901368777150, 75600<span class=o>)</span>
Minimum: <span class=m>1100</span> @ <span class=o>(</span>371764953656247878, 5957505246066178493, 661631939839983461, 1100<span class=o>)</span>

<span class=c1># p3.c</span>

Running
Test <span class=m>10000</span> cases use 13.122157096862793 seconds
Sum CPU cycles: <span class=m>12171000</span>
Average CPU cycles: 1217.1
Maximum: <span class=m>271900</span> @ <span class=o>(</span>7398188815938423410, 8253708753758420468, 4659411386263076728, 271900<span class=o>)</span>
Minimum: <span class=m>900</span> @ <span class=o>(</span>3809943949718199994, 3287343789103329664, 8650829315397374343, 900<span class=o>)</span>

<span class=c1># -O2</span>

<span class=c1># p1.c</span>

Running
Test <span class=m>10000</span> cases use 13.260606288909912 seconds
Sum CPU cycles: <span class=m>1001601100</span>
Average CPU cycles: 100160.11
Maximum: <span class=m>926300</span> @ <span class=o>(</span>339379419259308487, 3491644293891775690, 4785117665160931184, 926300<span class=o>)</span>
Minimum: <span class=m>87500</span> @ <span class=o>(</span>5052948108270793981, 27482781138671, 7792928891817598563, 87500<span class=o>)</span>

<span class=c1># p2.c</span>

Running
Test <span class=m>10000</span> cases use 12.278534412384033 seconds
Sum CPU cycles: <span class=m>14735700</span>
Average CPU cycles: 1473.57
Maximum: <span class=m>132100</span> @ <span class=o>(</span>7176780085212300945, 2291171313687225809, 7324459208582226040, 132100<span class=o>)</span>
Minimum: <span class=m>1000</span> @ <span class=o>(</span>9203745517614844759, 6874714748664006916, 67857160092233, 1000<span class=o>)</span>

<span class=c1># p3.c</span>

Running
Test <span class=m>10000</span> cases use 12.674974918365479 seconds
Sum CPU cycles: <span class=m>12079100</span>
Average CPU cycles: 1207.91
Maximum: <span class=m>202400</span> @ <span class=o>(</span>8532847693583176248, 6988877428537774137, 8782939934027677977, 202400<span class=o>)</span>
Minimum: <span class=m>900</span> @ <span class=o>(</span>3971319143760212181, 2705697508146050036, 1115671950010882609, 900<span class=o>)</span>
</code></pre></div></section><footer class=article-footer><section class=article-copyright><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-copyright" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><circle cx="12" cy="12" r="9"/><path d="M14.5 9a3.5 4 0 100 6"/></svg><span>Licensed under CC BY-NC-SA 4.0</span></section></footer><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/katex@0.13.13/dist/katex.min.css integrity=sha384-RZU/ijkSsFbcmivfdRBQDtwuwVqK7GMOw6IMvKyeWL2K5UAlyp6WonmB8m7Jd0Hn crossorigin=anonymous><script src=https://cdn.jsdelivr.net/npm/katex@0.13.13/dist/katex.min.js integrity=sha384-pK1WpvzWVBQiP0/GjnvRxV4mOb0oxFuyRxJlk6vVw146n3egcN5C925NCP7a7BY8 crossorigin=anonymous defer></script><script src=https://cdn.jsdelivr.net/npm/katex@0.13.13/dist/contrib/auto-render.min.js integrity=sha384-vZTG03m+2yp6N6BNi5iM4rW4oIwk5DfcNdFfxkk9ZWpDriOkXX8voJBFrAO7MpVl crossorigin=anonymous defer></script><script>window.addEventListener("DOMContentLoaded",()=>{renderMathInElement(document.querySelector(`.article-content`),{delimiters:[{left:"$$",right:"$$",display:!0},{left:"$",right:"$",display:!1},{left:"\\(",right:"\\)",display:!1},{left:"\\[",right:"\\]",display:!0}]})})</script></article><aside class=related-contents--wrapper><h2 class=section-title>Related contents</h2><div class=related-contents><div class="flex article-list--tile"><article><a href=/posts/learning/python-packaging/><div class=article-details><h2 class=article-title>Python 项目打包与分发</h2></div></a></article><article><a href=/posts/learning/rust-functional/><div class=article-details><h2 class=article-title>Rust 函数式编程</h2></div></a></article><article><a href=/posts/learning/rust-generic-types/><div class=article-details><h2 class=article-title>Rust 泛型</h2></div></a></article><article><a href=/posts/learning/rust-collections/><div class=article-details><h2 class=article-title>Rust 集合</h2></div></a></article><article><a href=/posts/learning/rust-modules/><div class=article-details><h2 class=article-title>Rust 模块与项目</h2></div></a></article></div></div></aside><script src=https://utteranc.es/client.js repo=StardustDL/stardustdl.github.io issue-term=pathname label=comment crossorigin=anonymous async></script><style>.utterances{max-width:unset}</style><script>function setUtterancesTheme(b){let a=document.querySelector('.utterances iframe');a&&a.contentWindow.postMessage({type:'set-theme',theme:`github-${b}`},'https://utteranc.es')}addEventListener('message',a=>{if(a.origin!=='https://utteranc.es')return;setUtterancesTheme(document.documentElement.dataset.scheme)}),window.addEventListener('onColorSchemeChange',a=>{setUtterancesTheme(a.detail)})</script><footer class=site-footer><section class=copyright>&copy;
2017 -
2021 StardustDL's Blog</section><section class=powerby><a style=color:gray href=http://www.beian.miit.gov.cn>冀ICP备19021004号</a><br>Built with <a href=https://gohugo.io/ target=_blank rel=noopener>Hugo</a><br>Theme <b><a href=https://github.com/CaiJimmy/hugo-theme-stack target=_blank rel=noopener data-version=3.5.0>Stack</a></b> designed by <a href=https://jimmycai.com target=_blank rel=noopener>Jimmy</a></section></footer><div class=pswp tabindex=-1 role=dialog aria-hidden=true><div class=pswp__bg></div><div class=pswp__scroll-wrap><div class=pswp__container><div class=pswp__item></div><div class=pswp__item></div><div class=pswp__item></div></div><div class="pswp__ui pswp__ui--hidden"><div class=pswp__top-bar><div class=pswp__counter></div><button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
<button class="pswp__button pswp__button--share" title=Share></button>
<button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
<button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button><div class=pswp__preloader><div class=pswp__preloader__icn><div class=pswp__preloader__cut><div class=pswp__preloader__donut></div></div></div></div></div><div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap"><div class=pswp__share-tooltip></div></div><button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)"></button>
<button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)"></button><div class=pswp__caption><div class=pswp__caption__center></div></div></div></div></div><script src=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo=" crossorigin=anonymous defer></script><script src=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU=" crossorigin=anonymous defer></script><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css integrity="sha256-c0uckgykQ9v5k+IqViZOZKc47Jn7KQil4/MP3ySA3F8=" crossorigin=anonymous><link rel=stylesheet href=https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.css integrity="sha256-SBLU4vv6CA6lHsZ1XyTdhyjJxCjPif/TRkjnsyGAGnE=" crossorigin=anonymous></main><aside class="sidebar right-sidebar sticky"><section class="widget archives"><div class=widget-icon><svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-hash" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentcolor" fill="none" stroke-linecap="round" stroke-linejoin="round"><path stroke="none" d="M0 0h24v24H0z"/><line x1="5" y1="9" x2="19" y2="9"/><line x1="5" y1="15" x2="19" y2="15"/><line x1="11" y1="4" x2="7" y2="20"/><line x1="17" y1="4" x2="13" y2="20"/></svg></div><h2 class="widget-title section-title">Table of contents</h2><div class=widget--toc><nav id=TableOfContents><ol><li><a href=#问题引入>问题引入</a></li><li><a href=#解决方法>解决方法</a><ol><li><a href=#运行环境>运行环境</a></li><li><a href=#基础设施>基础设施</a><ol><li><a href=#测试程序>测试程序</a></li><li><a href=#计时程序>计时程序</a></li><li><a href=#makefile>Makefile</a></li></ol></li><li><a href=#基准实现>基准实现</a></li><li><a href=#性能优化>性能优化</a><ol><li><a href=#优化1二进制拆分>优化1：二进制拆分</a></li><li><a href=#优化2高低位分别处理>优化2：高低位分别处理</a></li><li><a href=#效率实测>效率实测</a></li></ol></li></ol></li></ol></nav></div></section></aside></div><script src=https://cdn.jsdelivr.net/npm/node-vibrant@3.1.5/dist/vibrant.min.js integrity="sha256-5NovOZc4iwiAWTYIFiIM7DxKUXKWvpVEuMEPLzcm5/g=" crossorigin=anonymous defer></script><script type=text/javascript src=/ts/main.js defer></script><script>(function(){const a=document.createElement('link');a.href="https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap",a.type="text/css",a.rel="stylesheet",document.head.appendChild(a)})()</script></body></html>